/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package rndgen;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.*;



/** Class contains rho-Pollard's method of factorization
 *
 * @author Pykhteyev Alexander
 */
public class Rho_Pollard {
    private static final BigInteger ONE = BigInteger.ONE;
    private static final BigInteger TWO = new BigInteger("2");
    private static final BigInteger ZERO = BigInteger.ZERO;
    private static int degree = 2;
    
    private Rho_Pollard() {}
    /** Returns full factoring of numberStr 
     * 
     * @param numberStr String representation of numberStr must be factorized
     * @param xStr String representation of xStr 
     * @param aStr String representation of aStr
     * @return ArrayList with prime divisors
     * @throws NumberFormatException If numberStr contains not only numbers
     */
    public static ArrayList<BigInteger> getFullFactorization(String numberStr,String xStr,String aStr) throws NumberFormatException{
        ArrayList<BigInteger> numbers = new ArrayList<BigInteger>();
        BigInteger number = new BigInteger(numberStr);
        do {
            // get prime divisor of numberStr
            BigInteger primeNumber = getPrimeDivisor(numberStr,xStr,aStr);
            // if numberStr == prime divisor -> prime divisor add in ArrayList and return ArrayList with prime divisors
            if (new BigInteger(numberStr).divide(primeNumber).compareTo(ONE) == 0) {
                numbers.add(number);
                return numbers;
            }
            // if numberStr != prime divisor -> prime divisor add in ArrayList and get prime divisor of numberStr/prime divisor
            else {
            	//System.out.println("Rho_Pollard prime divisor " + primeNumber);
                numbers.add(primeNumber);
                number = number.divide(primeNumber);
                numberStr = number.toString();
            }
            
        } while(true);
        
        
    }
    /** Returns a prime divisor of numberStr by means of rho-Pollard method with complexity O(n^1/4)
     * 
     * @param numberStr String representation of numberStr must be factorized
     * @param xStr String representation of xStr 
     * @param aStr String representation of aStr
     * @return A prime divisor of numberStr
     * @throws NumberFormatException If numberStr contains not only numbers
     */
    public static BigInteger getPrimeDivisor(String numberStr,String xStr,String aStr) throws NumberFormatException {
        //Choose equation: f(x) = (x^2 + a) mod numberStr 
        
        //String representation -> BigInteger
        BigInteger number = new BigInteger(numberStr);
        //Prime checking with help Rabin-Miller's 
        
        BigInteger x0 = new BigInteger(xStr);
        BigInteger a = new BigInteger(aStr);
        if (number.isProbablePrime(4)) {
            return number;
        }
        //Checking even numberStr
        if (number.mod(TWO).compareTo(ZERO) == 0) {
            return TWO;
        }
        //xI = f(x); x2I = f(f(x))
        BigInteger gcd;//GCD - Greatest Common Divisor
        BigInteger xI = x0.pow(degree).add(a).mod(number);//xI
        BigInteger x2I = xI.pow(degree).add(a).mod(number);//x2I
        
        do {
            //Find GCD
            gcd = xI.add(x2I.negate()).gcd(number);
            //if  1 < GCD < numberStr then 2 divisors are found
            if (gcd.compareTo(BigInteger.ONE) != 0 && gcd.compareTo(number) !=0 ) {                     
                // if numberStr/GCD is prime divisor then method return number/GCD 
                if (number.divide(gcd).isProbablePrime(4)) {
                    return number.divide(gcd);
                }
                else {
                    //if GCD is prime divisor then method return GCD
                    if (gcd.isProbablePrime(4)) {
                        return gcd;
                    } 
                    //if GCD and numberStr/GCD are not prime divisors then get prime divisor of GCD 
                    else {
                        return getPrimeDivisor(gcd.toString(),xStr,aStr);
                    }
                    
                }
            }
            //xI = f(x); x2I = f(f(x))
            xI = xI.pow(degree).add(a).mod(number);
            x2I = x2I.pow(degree).add(a).mod(number).pow(degree).add(a).mod(number);
            //if xI==x2I then f(x) = x^degree + 1  1 < degree < 10
            /**if (xI.compareTo(x2I) == 0) {
                a = new Random().nextInt(10);
            }**/
            
        } while (true);
    }
}